{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #数组的相对排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #counting-sort #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #计数排序 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: relativeSortArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组的相对排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个数组，<code>arr1</code> 和&nbsp;<code>arr2</code>，</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>arr2</code>&nbsp;中的元素各不相同</li>\n",
    "\t<li><code>arr2</code> 中的每个元素都出现在&nbsp;<code>arr1</code>&nbsp;中</li>\n",
    "</ul>\n",
    "\n",
    "<p>对 <code>arr1</code>&nbsp;中的元素进行排序，使 <code>arr1</code> 中项的相对顺序和&nbsp;<code>arr2</code>&nbsp;中的相对顺序相同。未在&nbsp;<code>arr2</code>&nbsp;中出现过的元素需要按照升序放在&nbsp;<code>arr1</code>&nbsp;的末尾。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]\n",
    "<strong>输出：</strong>[2,2,2,1,4,3,3,9,6,7,19]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr1.length, arr2.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= arr1[i], arr2[i] &lt;= 1000</code></li>\n",
    "\t<li><code>arr2</code>&nbsp;中的元素&nbsp;<code>arr2[i]</code>&nbsp;各不相同</li>\n",
    "\t<li><code>arr2</code> 中的每个元素&nbsp;<code>arr2[i]</code>&nbsp;都出现在&nbsp;<code>arr1</code>&nbsp;中</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 1122&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/relative-sort-array/\">https://leetcode-cn.com/problems/relative-sort-array/</a>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [0H97ZC](https://leetcode.cn/problems/0H97ZC/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [0H97ZC](https://leetcode.cn/problems/0H97ZC/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,1,3,2,4,6,7,9,2,19]\\n[2,1,4,3,9,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        c = collections.Counter(arr1)\n",
    "        ans = []\n",
    "        for i in range(len(arr2)):\n",
    "            ans += [arr2[i]] * c[arr2[i]]\n",
    "        \n",
    "        t = []\n",
    "        for i in range(len(arr1)):\n",
    "            if arr1[i] not in arr2:\n",
    "                t.append(arr1[i])\n",
    "        \n",
    "        return ans + list(sorted(t))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr = [0] * 1001\n",
    "        for val in arr1:\n",
    "            arr[val] += 1\n",
    "        res = []\n",
    "        for val in arr2:\n",
    "            while arr[val] > 0:\n",
    "                res.append(val)\n",
    "                arr[val] -= 1\n",
    "        for i in range(len(arr)):\n",
    "            while arr[i] > 0:\n",
    "                res.append(i)\n",
    "                arr[i] -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        # sign,lenarr1=0,len(arr1)\n",
    "        # for i in range(len(arr2)):\n",
    "        #     for j in range(sign,lenarr1):\n",
    "        #         if arr1[j]==arr2[i]:\n",
    "        #             a=arr1[sign]\n",
    "        #             arr1[sign]=arr1[j]\n",
    "        #             arr1[j]=a\n",
    "        #             sign+=1\n",
    "        # if sign+1==lenarr1:\n",
    "        #     return arr1\n",
    "        # else:\n",
    "        #     for x in range(lenarr1-sign-1):\n",
    "        #         print('x:',x)\n",
    "        #         for y in range(sign,lenarr1-x-1):\n",
    "        #             if arr1[y]>arr1[y+1]:\n",
    "        #                 print('进入',arr1[y],arr1[y+1])\n",
    "        #                 aa=arr1[y]\n",
    "        #                 arr1[y]=arr1[y+1]\n",
    "        #                 arr1[y+1]=aa\n",
    "        #     return arr1\n",
    "        arr = [0 for _ in range(max(arr1)+1)]  \n",
    "        ans = []  \n",
    "        for i in range(len(arr1)):  \n",
    "            arr[arr1[i]] += 1 \n",
    "        for i in range(len(arr2)): \n",
    "            while arr[arr2[i]] > 0: \n",
    "                ans.append(arr2[i]) \n",
    "                arr[arr2[i]] -= 1 \n",
    "        for i in range(len(arr)): \n",
    "            while arr[i] > 0:  \n",
    "                ans.append(i)\n",
    "                arr[i] -= 1\n",
    "        return ans \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr3=[] \n",
    "        arr4=[]\n",
    "        for i in range(0,len(arr2)):\n",
    "            for j in range(0,len(arr1)):\n",
    "                if arr1[j] in arr2: \n",
    "                    if arr2.index(arr1[j])==i:\n",
    "                        arr3.append(arr1[j])\n",
    "                else:\n",
    "                    if i==0:\n",
    "                        arr4.append(arr1[j])\n",
    "        arr4.sort()\n",
    "        for i in arr4:\n",
    "            arr3.append(i)\n",
    "        return arr3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        x=[]\n",
    "        y=[]\n",
    "        for i in arr1:\n",
    "            if i in arr2:\n",
    "                x.append(i)\n",
    "            else:\n",
    "                y.append(i)\n",
    "        x.sort(key=lambda i:arr2.index(i))\n",
    "        y.sort()\n",
    "        return x+y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        record = {num: i for i, num in enumerate(arr2)}\n",
    "        n = max(arr2)\n",
    "        for i, num in enumerate(arr1):\n",
    "            if num not in record:\n",
    "                record[num] = n + num\n",
    "        arr1.sort(key=lambda x : record[x])\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        book = {}\n",
    "        for num in arr1:\n",
    "            if num in book:\n",
    "                book[num] += 1\n",
    "            else:\n",
    "                book[num] = 1\n",
    "        result = []\n",
    "        for num in arr2:\n",
    "            result += ([num] * book.pop(num))\n",
    "        keys = list(book.keys())\n",
    "        keys.sort()\n",
    "        for key in keys:\n",
    "            result += ([key] * book[key])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        rnk = defaultdict(int)\n",
    "        for i, num in enumerate(arr2) :\n",
    "            rnk[num] = i\n",
    "        arr1.sort(key = lambda x : (0, rnk[x]) if x in rnk else (1, x))\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        # 字典：arr1的元素和个数\n",
    "        # 遍历arr2,将符合的全部加入结果列表。加入后移除字典中对应的键值对。\n",
    "        # 遍历字典。将剩余的值重新排序，并入结果列表\n",
    "        tmp_dict = dict(collections.Counter(arr1))\n",
    "        result = []\n",
    "        for i in arr2:\n",
    "            if i in tmp_dict:\n",
    "                loop = tmp_dict[i]\n",
    "                for count in range(loop):\n",
    "                    result.append(i)\n",
    "                tmp_dict.pop(i)\n",
    "\n",
    "        others = [k for k, v in tmp_dict.items() for i in range(v)]\n",
    "        others.sort()\n",
    "\n",
    "        return result + others"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr3=[]\n",
    "        for i in arr2:\n",
    "            arr3+=[i]*arr1.count(i)\n",
    "            r=0\n",
    "            for l in range(len(arr1)):\n",
    "                if arr1[l-r]==i:\n",
    "                    del arr1[l-r]\n",
    "                    r+=1\n",
    "        for _ in arr1[:-1]:\n",
    "            for i in range(len(arr1)-1):\n",
    "                if arr1[i]>arr1[i+1]:\n",
    "                    arr1[i],arr1[i+1]=arr1[i+1],arr1[i]\n",
    "        arr3+=arr1\n",
    "        return arr3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr = [0] * 1001\n",
    "        for val in arr1:\n",
    "            arr[val] += 1\n",
    "        res = []\n",
    "        for val in arr2:\n",
    "            while arr[val] > 0:\n",
    "                res.append(val)\n",
    "                arr[val] -= 1\n",
    "        for i in range(len(arr)):\n",
    "            while arr[i] > 0:\n",
    "                res.append(i)\n",
    "                arr[i] -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "    #     arr3 = list(filter(lambda x: x not in arr2, arr1))\n",
    "    #     result = []\n",
    "    #     arr = []\n",
    "    #     for i in arr2:\n",
    "    #         res = list(filter(lambda x: x == i, arr1))\n",
    "    #         result += res\n",
    "    #     arr3.sort()\n",
    "    #     result += arr3\n",
    "    #     return result\n",
    "\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        rank = {x: i for i, x in enumerate(arr2)}\n",
    "        return sorted(arr1, key=lambda x: (rank.get(x, float('inf')), x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        def mycmp(x: int) -> (int, int):\n",
    "            return rank[x] if x in rank else x\n",
    "        \n",
    "        n = len(arr2)\n",
    "        # i-n 负的，x正的\n",
    "        rank = {x: i - n for i, x in enumerate(arr2)}\n",
    "        arr1.sort(key=mycmp)\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        h = {i: v for v, i in enumerate(arr2)}\n",
    "\n",
    "        return sorted(arr1, key=lambda x: h.get(x, 10000 + x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        mn = max(arr1)\n",
    "        f = [0] * (mn + 1)\n",
    "        for x in arr1:\n",
    "            f[x] += 1\n",
    "        ans = []\n",
    "        for x in arr2:\n",
    "            ans += [x] * f[x]\n",
    "            f[x] = 0\n",
    "        for i in range(mn + 1):\n",
    "            if f[i]:\n",
    "                ans += [i] * f[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        ans1 = []\n",
    "        ans2 = []\n",
    "        for i in arr2:\n",
    "            for j in arr1:\n",
    "                if i==j:\n",
    "                    ans1.append(i)\n",
    "        for i in arr1:\n",
    "            if i not in arr2:\n",
    "                ans2.append(i)\n",
    "        ans2.sort()\n",
    "        return ans1+ans2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        dic = {}\n",
    "        print(arr1)\n",
    "        for i in arr2:\n",
    "            dic[i] = 0\n",
    "        temp = []\n",
    "        for i in arr1:\n",
    "            if i not in dic:\n",
    "                temp.append(i)\n",
    "            else:\n",
    "                dic[i] += 1\n",
    "        temp.sort()\n",
    "        index = 0\n",
    "        for i in dic:\n",
    "            for j in range(dic[i]):\n",
    "                arr1[index] = i\n",
    "                index += 1\n",
    "        for i in temp:\n",
    "            arr1[index] = i\n",
    "            index += 1\n",
    "        \n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr = [0 for _ in range(1001)]\n",
    "        ans = []\n",
    "        for i in range(len(arr1)):\n",
    "            arr[arr1[i]] += 1\n",
    "        for i in range(len(arr2)):\n",
    "            while arr[arr2[i]] > 0:\n",
    "                ans.append(arr2[i])\n",
    "                arr[arr2[i]] -= 1\n",
    "        for i in range(len(arr)):\n",
    "            while arr[i] > 0:\n",
    "                ans.append(i)\n",
    "                arr[i] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        count_dict=collections.Counter(arr1)\n",
    "        arr1_length=len(arr1)\n",
    "        diff=sorted(list(set(arr1)-set(arr2)))\n",
    "        #print(diff)\n",
    "        count=0\n",
    "        for i in arr2:\n",
    "            i_count=count_dict.get(i,0)\n",
    "            for j in range(i_count):\n",
    "                arr1[count]=i\n",
    "                count+=1\n",
    "        for i in diff:\n",
    "            i_count=count_dict.get(i,0)\n",
    "            for j in range(i_count):\n",
    "                arr1[count]=i\n",
    "                count+=1\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr1_dic = {}\n",
    "        for val in arr1:\n",
    "            arr1_dic[val] = arr1_dic.get(val, 0) + 1\n",
    "\n",
    "        res = []\n",
    "        for v in arr2:\n",
    "            if v in arr1_dic:\n",
    "                res.extend([v] * arr1_dic[v])\n",
    "                del arr1_dic[v]\n",
    "\n",
    "        new_arr1_dic = sorted(arr1_dic.items(), key=lambda s: s[0])\n",
    "        for v1, freq in new_arr1_dic:\n",
    "            res.extend([v1] * freq)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        tnp = collections.Counter()\n",
    "        c = collections.Counter(arr1)\n",
    "        for k in list(c.keys()):\n",
    "            if k not in arr2:\n",
    "                tnp[k] = c[k]\n",
    "                del c[k]\n",
    "        for k,v in c.items():\n",
    "            if v!= 1:\n",
    "                while v-1:\n",
    "                    arr2.insert(arr2.index(k),k)\n",
    "                    v -= 1\n",
    "        print(tnp)\n",
    "        print(c)\n",
    "        tnp = sorted(tnp.items(), key=lambda d: d[0])\n",
    "        for k,v in dict(tnp).items():\n",
    "            while v:\n",
    "                arr2.append(k)\n",
    "                v -= 1\n",
    "        return arr2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        counting_sort_list = [0]*1001\n",
    "        res = []\n",
    "        for i in arr1:\n",
    "            counting_sort_list[i] += 1\n",
    "        for i in arr2:\n",
    "            while counting_sort_list[i] != 0:\n",
    "                res.append(i)\n",
    "                counting_sort_list[i] -= 1\n",
    "        for i in range(1, len(counting_sort_list)):\n",
    "            while counting_sort_list[i] != 0:\n",
    "                res.append(i)\n",
    "                counting_sort_list[i] -=1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        dic = Counter(arr1)\n",
    "        res=[]\n",
    "        for num in arr2:\n",
    "            while dic[num]:\n",
    "                res.append(num)\n",
    "                dic[num]-=1\n",
    "        dic1=sorted(dic.items(), key = lambda x: x[0])\n",
    "        for k,v in dic1:\n",
    "            if v==0:\n",
    "                continue\n",
    "            else:\n",
    "                while v:\n",
    "                    res.append(k)\n",
    "                    v-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr = [0 for _ in range(1001)]  \n",
    "        ans = []  \n",
    "        for i in range(len(arr1)):  \n",
    "            arr[arr1[i]] += 1 \n",
    "        for i in range(len(arr2)): \n",
    "            while arr[arr2[i]] > 0: \n",
    "                ans.append(arr2[i]) \n",
    "                arr[arr2[i]] -= 1 \n",
    "        for i in range(len(arr)): \n",
    "            while arr[i] > 0:  \n",
    "                ans.append(i)\n",
    "                arr[i] -= 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        nums = [0] * 1001\n",
    "        for x in arr1:\n",
    "            nums[x] += 1\n",
    "        ans = []\n",
    "        for x in arr2:\n",
    "            while nums[x] > 0:\n",
    "                ans.append(x)\n",
    "                nums[x] -= 1\n",
    "        for i in range(1001):\n",
    "            while nums[i] > 0:\n",
    "                ans.append(i)\n",
    "                nums[i] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        \n",
    "        # 创建一个字典来统计arr1中每个元素出现的次数\n",
    "        count_map = {}\n",
    "        for num in arr1:\n",
    "            count_map[num] = count_map.get(num, 0) + 1\n",
    "        \n",
    "        # 根据arr2的顺序和arr1中的频率对arr1进行排序\n",
    "        res = []\n",
    "        for num in arr2:\n",
    "            res += [num] * count_map.pop(num)\n",
    "        \n",
    "        # 将未出现在 arr2 中的元素按升序添加到结果中\n",
    "        for num in sorted(count_map):\n",
    "            res.extend([num] * count_map[num])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        # 字典cnt_dict\n",
    "        # 将arr2中的元素放入字典arr2_dict中，\n",
    "        # 遍历arr1，如果元素e在arr2_dict中，则把e已经其出现次数加入到cnt_dict中\n",
    "        #           如果元素e不在arr2_dict中，则把元素存储在堆中\n",
    "        # 再遍历arr2从cnt_dict中把元素存储到tmp中，结束之后再把堆中的元素放入到tmp中\n",
    "\n",
    "        tmp = []\n",
    "        res = []\n",
    "        cnt_dict = {}\n",
    "        arr2_dict = set(arr2)\n",
    "        for e in arr1:\n",
    "            if e in arr2_dict:\n",
    "                if e in cnt_dict:\n",
    "                    cnt_dict.update({e: cnt_dict.get(e) + 1})\n",
    "                else:\n",
    "                    cnt_dict.update({e: 1})\n",
    "            else:\n",
    "                tmp.append(e)\n",
    "        heapq.heapify(tmp)\n",
    "        print(\"标准：\", tmp)\n",
    "        for e in arr2:\n",
    "            cnt = cnt_dict.get(e)\n",
    "            for _ in range(0, cnt):\n",
    "                res.append(e)\n",
    "        for _ in range(0, len(tmp)):\n",
    "            res.append(heapq.heappop(tmp))\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        rank = {x: i for i, x in enumerate(arr2)}\n",
    "        return sorted(arr1, key=lambda x: (rank.get(x, float('inf')), x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        list1 = [item for item in arr1 if item in arr2]\n",
    "        list2 = [item for item in arr1 if item not in arr2]\n",
    "        list1.sort(key=arr2.index)\n",
    "        list2.sort()\n",
    "        return list1+list2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        counter = [0] * 1001\n",
    "        res = []\n",
    "        for i in range(len(arr1)):\n",
    "            counter[arr1[i]] += 1\n",
    "        for each in arr2:\n",
    "            while counter[each]>0:\n",
    "                res.append(each)\n",
    "                counter[each] -= 1\n",
    "        for j in range(len(counter)):\n",
    "            while counter[j]>0:\n",
    "                res.append(j)\n",
    "                counter[j]-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        mp = {num: i for i, num in enumerate(arr2)}\n",
    "        arr1.sort(key=lambda x: (mp.get(x, 10000), x))\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        map_ = {\n",
    "            num: i for i, num in enumerate(arr2)\n",
    "        }\n",
    "        set_arr1 = set(arr1)\n",
    "        for item in set_arr1:\n",
    "            if item in map_:\n",
    "                continue\n",
    "            else:\n",
    "                map_[item] = item + 1000\n",
    "        return sorted(arr1, key=lambda x: map_[x])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        def mycmp(x: int) -> (int, int):\n",
    "            return rank[x] if x in rank else x\n",
    "        \n",
    "        n = len(arr2)\n",
    "        rank = {x: i - n for i, x in enumerate(arr2)}\n",
    "        arr1.sort(key=mycmp)\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        extend_list = []\n",
    "        extend_result = []\n",
    "        for i in arr1:\n",
    "            if i not in arr2:\n",
    "                extend_list.append(i)\n",
    "        extend_list.sort()\n",
    "        for i in arr2:\n",
    "            for j in arr1:\n",
    "                if i == j:\n",
    "                    extend_result.append(j)\n",
    "        extend_result.extend(extend_list)\n",
    "        return extend_result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        dic = Counter(arr1)\n",
    "        res=[]\n",
    "        for num in arr2:\n",
    "            while dic[num]:\n",
    "                res.append(num)\n",
    "                dic[num]-=1\n",
    "        dic1=sorted(dic.items(), key = lambda x: x[0])\n",
    "        for k,v in dic1:\n",
    "            if v==0:\n",
    "                continue\n",
    "            else:\n",
    "                while v:\n",
    "                    res.append(k)\n",
    "                    v-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        # 字典cnt_dict\n",
    "        # 将arr2中的元素放入字典arr2_dict中，\n",
    "        # 遍历arr1，如果元素e在arr2_dict中，则把e已经其出现次数加入到cnt_dict中\n",
    "        #           如果元素e不在arr2_dict中，则把元素存储在堆中\n",
    "        # 再遍历arr2从cnt_dict中把元素存储到tmp中，结束之后再把堆中的元素放入到tmp中\n",
    "\n",
    "        tmp = []\n",
    "        res = []\n",
    "        cnt_dict = {}\n",
    "        arr2_dict = set(arr2)\n",
    "        for e in arr1:\n",
    "            if e in arr2_dict:\n",
    "                if e in cnt_dict:\n",
    "                    cnt_dict.update({e: cnt_dict.get(e) + 1})\n",
    "                else:\n",
    "                    cnt_dict.update({e: 1})\n",
    "            else:\n",
    "                tmp.append(e)\n",
    "        heapq.heapify(tmp)\n",
    "        for e in arr2:\n",
    "            cnt = cnt_dict.get(e)\n",
    "            for _ in range(0, cnt):\n",
    "                res.append(e)\n",
    "        for _ in range(0, len(tmp)):\n",
    "            res.append(heapq.heappop(tmp))\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        ans=[]\n",
    "        cnt=[0]*1001\n",
    "        for i in arr1:\n",
    "            cnt[i]+=1\n",
    "        for i in arr2:\n",
    "            ans.extend([i]*cnt[i])\n",
    "            cnt[i]=0\n",
    "        for i in range(1001):\n",
    "            if cnt[i]!=0:\n",
    "                ans.extend([i]*cnt[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr = [0] * 1001\n",
    "        for val in arr1:\n",
    "            arr[val] += 1\n",
    "        res = []\n",
    "        for val in arr2:\n",
    "            while arr[val] > 0:\n",
    "                res.append(val)\n",
    "                arr[val] -= 1\n",
    "        for i in range(len(arr)):\n",
    "            while arr[i] > 0:\n",
    "                res.append(i)\n",
    "                arr[i] -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        index_dict = {value: index for index, value in enumerate(arr2)}\n",
    "        arr1.sort(key=lambda x: (index_dict[x] if x in index_dict else len(arr2) + x))\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        while arr2:\n",
    "            va = arr2.pop(0)\n",
    "            while va in arr1:\n",
    "                arr1.remove(va)\n",
    "                ans.append(va)\n",
    "        return ans + sorted(arr1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        upper = max(arr1)\n",
    "        frequency = [0] * (upper + 1)\n",
    "        for x in arr1:\n",
    "            frequency[x] += 1\n",
    "        \n",
    "        ans = list()\n",
    "        for x in arr2:\n",
    "            ans.extend([x] * frequency[x])\n",
    "            frequency[x] = 0\n",
    "        for x in range(upper + 1):\n",
    "            if frequency[x] > 0:\n",
    "                ans.extend([x] * frequency[x])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        a=[]\n",
    "        b=list(arr1)\n",
    "        for i in arr2:\n",
    "            for x in arr1:\n",
    "                if i==x:\n",
    "                   a.append(x)\n",
    "                   b.remove(x)\n",
    "        b.sort()\n",
    "        return a+b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        d = dict()\n",
    "        rest = dict()\n",
    "        for v in arr1:\n",
    "            if v in arr2:\n",
    "                if v not in d:\n",
    "                    d[v] = 1\n",
    "                else:\n",
    "                    d[v] += 1\n",
    "            else:\n",
    "                if v not in rest:\n",
    "                    rest[v] =1\n",
    "                else:\n",
    "                    rest[v] += 1\n",
    "        res = []\n",
    "        visited = []\n",
    "        for v in arr2:\n",
    "            if v in d and v not in visited:\n",
    "                visited.append(v)\n",
    "                for x in range(d[v]):\n",
    "                    res.append(v)\n",
    "        if list(rest.keys()) == []:\n",
    "            return res\n",
    "        else:\n",
    "            load = sorted(rest.items(), key = lambda x:x[0])\n",
    "            for i, j in load:\n",
    "                for k in range(j):\n",
    "                    res.append(i)\n",
    "            return res\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        map = [0 for _ in range(1001)]\n",
    "        res = [0 for _ in range(len(arr1))]\n",
    "        loc = 0\n",
    "        for i in arr1:\n",
    "            map[i] += 1\n",
    "        # 按照arr2的顺序，填充数字\n",
    "        for i in range(len(arr2)):\n",
    "            while (map[arr2[i]] > 0):\n",
    "                res[loc] = arr2[i]\n",
    "                map[arr2[i]] -= 1\n",
    "                loc += 1\n",
    "        # 未出现的数字，需要按照升序排列，所以，我们从0 ~ 1001遍历\n",
    "        for i in range(len(map)):\n",
    "            while (map[i] > 0):\n",
    "                res[loc] = i\n",
    "                map[i] -= 1\n",
    "                loc += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        if arr2 is None:\n",
    "            return arr1\n",
    "        count_dict = {}\n",
    "        for num in arr1:\n",
    "            count_dict[num] = count_dict.get(num, 0) + 1\n",
    "\n",
    "        res = []\n",
    "        for num in arr2:\n",
    "            res.extend([num] * count_dict[num])\n",
    "            count_dict.pop(num)\n",
    "\n",
    "        remaining_nums = sorted(count_dict.keys())\n",
    "        for num in remaining_nums:\n",
    "            res.extend([num] * count_dict[num])\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        rank = {x: i for i, x in enumerate(arr2)}\n",
    "        arr1.sort(key=lambda x: (0,rank[x]) if x in rank else (1, x))\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "    #     arr3 = list(filter(lambda x: x not in arr2, arr1))\n",
    "    #     result = []\n",
    "    #     arr = []\n",
    "    #     for i in arr2:\n",
    "    #         res = list(filter(lambda x: x == i, arr1))\n",
    "    #         result += res\n",
    "    #     arr3.sort()\n",
    "    #     result += arr3\n",
    "    #     return result\n",
    "\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        def mycmp(x):\n",
    "            return (0, rank[x]) if x in rank else (1, x)\n",
    "\n",
    "\n",
    "        rank = {x : i for i, x in enumerate(arr2)}\n",
    "   \n",
    "        arr1.sort(key=mycmp)\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        ct=dict()\n",
    "        notins=set()\n",
    "        arr2set=set(arr2)\n",
    "        for i in arr1:\n",
    "            if i in ct:ct[i]+=1\n",
    "            else:ct[i]=1\n",
    "            if i not in arr2set:\n",
    "                notins.add(i )\n",
    "        ans=[]\n",
    "        for i in arr2:\n",
    "            ans=ans+[i]*ct[i]\n",
    "        notinlt=list(notins)\n",
    "        notinlt.sort()\n",
    "        for i in notinlt:\n",
    "            ans=ans+[i]*ct[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        idx = {x: i for i, x in enumerate(arr2)}\n",
    "        arr1.sort(key=lambda x:(idx.get(x, inf), x))\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "#         # a=[0]*1000\n",
    "#         res=[]\n",
    "#         a=[0 for _ in range(1001)]\n",
    "#         for i in range(len(arr1)):\n",
    "#             a[arr1[i]]+=1\n",
    "#         # print(a)\n",
    "#         for i in range(len(arr2)):\n",
    "#             while a[arr2[i]]>0:\n",
    "#                 res.append(arr2[i])\n",
    "#                 a[arr2[i]]-=1\n",
    "#         # a 的下标，就是 arr1[]的值，题目要求剩下的元素升序排列，所以如果有剩下的值，按顺序从小到大找和添加就行。\n",
    "#         for i in range(len(a)):\n",
    "#             while a[i]>0:\n",
    "#                 # a 里面的 i,索引值就等于 arr1 的值。\n",
    "#                 res.append(i)\n",
    "#                 a[i]-=1\n",
    "#         return res\n",
    "# class Solution:\n",
    "#     def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "#         # 拆分\n",
    "#         dic = {}\n",
    "#         # list1 = []\n",
    "#         list2=arr1\n",
    "#         # print(list2)\n",
    "#         for i in arr2:\n",
    "\n",
    "#             for j in range(len(arr1)):\n",
    "\n",
    "#                 if arr1[j] == i:\n",
    "#                     dic[i] = dic.get(i, 0) + 1\n",
    "#                     # list2.remove(i)\n",
    "#         # print(list2)\n",
    "#             # list1.append(arr1[j])\n",
    "#         # print(dic)\n",
    "#         res = []\n",
    "#         for m in arr2:\n",
    "#             # print(dic[m])\n",
    "#             for n in range(dic[m]):\n",
    "#                 res.append(m)\n",
    "#                 list2.remove(m)\n",
    "#         # print(res)\n",
    "#         # print(list2)\n",
    "#         list2.sort()\n",
    "#         res.extend(list2)\n",
    "#         return res\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        res = [0] * 1001\n",
    "        ans = []\n",
    "        for i in arr1:\n",
    "            res[i] += 1\n",
    "        for i in arr2:\n",
    "            for j in range(res[i]):\n",
    "                ans.append(i)\n",
    "                res[i] -= 1\n",
    "        for i in range(len(res)):\n",
    "            while res[i]>0:\n",
    "                ans.append(i)\n",
    "                res[i]-=1\n",
    "        print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        map = [0 for _ in range(1001)]\n",
    "        res = [0 for _ in range(len(arr1))]\n",
    "        loc = 0\n",
    "        for i in arr1:\n",
    "            map[i] += 1\n",
    "        \n",
    "        for i in range(len(arr2)):\n",
    "            while (map[arr2[i]] > 0):\n",
    "                res[loc] = arr2[i]\n",
    "                map[arr2[i]] -= 1\n",
    "                loc += 1\n",
    "        \n",
    "        for i in range(len(map)):\n",
    "            while (map[i] > 0):\n",
    "                res[loc] = i\n",
    "                map[i] -= 1\n",
    "                loc += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        def mycmp(x):\n",
    "            return (0, rank[x]) if x in rank else (1, x)\n",
    "\n",
    "\n",
    "        rank = {x : i for i, x in enumerate(arr2)}\n",
    "        arr1.sort(key=mycmp)\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        d = {v:i for i, v in enumerate(arr2)}\n",
    "        arr1.sort(key = lambda x: (d.get(x, len(arr2)), x))\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr = [0 for _ in range(1001)]  \n",
    "        ans = []  \n",
    "        for i in range(len(arr1)):  \n",
    "            arr[arr1[i]] += 1 \n",
    "        for i in range(len(arr2)): \n",
    "            while arr[arr2[i]] > 0: \n",
    "                ans.append(arr2[i]) \n",
    "                arr[arr2[i]] -= 1 \n",
    "        for i in range(len(arr)): \n",
    "            while arr[i] > 0:  \n",
    "                ans.append(i)\n",
    "                arr[i] -= 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        def mycmp(x):\n",
    "            return rank[x] if x in rank else x\n",
    "        n = len(arr2)\n",
    "        rank = {x: i - n for i, x in enumerate(arr2)}\n",
    "        arr1.sort(key=mycmp)\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        upper = max(arr1)\n",
    "        f = [0] * (upper + 1)\n",
    "        for x in arr1:\n",
    "            f[x] += 1\n",
    "        ans = []\n",
    "        for x in arr2:\n",
    "            ans.extend([x] * f[x])\n",
    "            f[x] = 0\n",
    "        for x in range(upper + 1):\n",
    "            if f[x] > 0:\n",
    "                ans.extend([x] * f[x])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        left = 0\n",
    "        idx = 0\n",
    "        while left < len(arr1) and idx < len(arr2):\n",
    "            right = left\n",
    "            while right < len(arr1):\n",
    "                if arr1[right] == arr2[idx]:\n",
    "                    arr1[left], arr1[right] = arr1[right], arr1[left]\n",
    "                    left += 1\n",
    "                right += 1\n",
    "            idx += 1\n",
    "        return arr1[:left] + sorted(arr1[left:])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr3 = []\n",
    "        for i in arr2:\n",
    "            for j in range(len(arr1)):\n",
    "                if i == arr1[j]:\n",
    "                    print(i)\n",
    "                    arr3.append(i)\n",
    "                    arr1[j] = -1\n",
    "        arr1.sort()\n",
    "        for i in arr1:\n",
    "            if i != -1:\n",
    "                arr3.append(i)\n",
    "        return arr3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr = [0 for _ in range(1001)]  \n",
    "        ans = []  \n",
    "        for i in range(len(arr1)):  \n",
    "            arr[arr1[i]] += 1 \n",
    "        for i in range(len(arr2)): \n",
    "            while arr[arr2[i]] > 0: \n",
    "                ans.append(arr2[i]) \n",
    "                arr[arr2[i]] -= 1 \n",
    "        for i in range(len(arr)): \n",
    "            while arr[i] > 0:  \n",
    "                ans.append(i)\n",
    "                arr[i] -= 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        while arr2:\n",
    "            va = arr2.pop(0)\n",
    "            while va in arr1:\n",
    "                arr1.remove(va)\n",
    "                ans.append(va)\n",
    "        return ans + sorted(arr1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        left = 0\n",
    "        idx = 0\n",
    "        while left < len(arr1) and idx < len(arr2):\n",
    "            right = left\n",
    "            while right < len(arr1):\n",
    "                if arr1[right] == arr2[idx]:\n",
    "                    arr1[left], arr1[right] = arr1[right], arr1[left]\n",
    "                    left += 1\n",
    "                right += 1\n",
    "            idx += 1\n",
    "        return arr1[:left] + sorted(arr1[left:])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        ma = max(arr1)\n",
    "        fre = [0] * (ma + 1)\n",
    "        for num in arr1:\n",
    "            fre[num] += 1\n",
    "        ans = []\n",
    "        for num in arr2:\n",
    "            ans.extend([num] * fre[num])\n",
    "            fre[num] = 0\n",
    "        for i in range(ma + 1):\n",
    "            if fre[i] > 0:\n",
    "                ans.extend([i] * fre[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        n1 = len(arr1)\n",
    "        n2 = len(arr2)\n",
    "        x = []\n",
    "        y = []\n",
    "        z = []\n",
    "        for i in range(n2):\n",
    "            y.append(0)\n",
    "        for i in range(n1):\n",
    "            if arr1[i] in arr2:\n",
    "                m = arr2.index(arr1[i])\n",
    "                y[m] = y[m]+1\n",
    "            else:\n",
    "                z.append(arr1[i])\n",
    "        z.sort()\n",
    "        for i in range(n2):\n",
    "            a = y[i]\n",
    "            for a1 in range(a):\n",
    "                x.append(arr2[i])\n",
    "        x = x +z\n",
    "        return x\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        dict = {'end': []}\n",
    "        max_index = len(arr2) - 1\n",
    "        for each1 in arr1:\n",
    "            if each1 in arr2:\n",
    "                for index in range(len(arr2)):\n",
    "                    if arr2[index] == each1:\n",
    "                        if index not in dict.keys():\n",
    "                            dict[index] = []\n",
    "                        \n",
    "                        dict[index].append(each1)\n",
    "                        print(dict)\n",
    "                        if max_index < index:\n",
    "                            max_index = index\n",
    "            else:\n",
    "                dict['end'].append(each1)\n",
    "        end = sorted(dict['end'])\n",
    "        res = []\n",
    "        for i in range(max_index + 1):\n",
    "            res = res + dict[i]\n",
    "        res = res + end\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        #哈希表\n",
    "        hash1 = {}\n",
    "        set1 = set(arr2)\n",
    "        l1 = []\n",
    "        l2 = []\n",
    "        for i in range (len(arr1)):\n",
    "            if arr1[i] not in hash1:\n",
    "                hash1[arr1[i]] = 1\n",
    "            else:\n",
    "                hash1[arr1[i]] += 1\n",
    "            if arr1[i] not in set1:\n",
    "                l2.append(arr1[i])\n",
    "        for i in range (len(arr2)):\n",
    "            l1 += [arr2[i]] * hash1[arr2[i]]\n",
    "        l2.sort()\n",
    "        return l1 + l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        rank = {x: i for i, x in enumerate(arr2)}\n",
    "\n",
    "        def mycmp(x: int) -> (int, int):\n",
    "            return (0, rank[x]) if x in rank else (1, x)\n",
    "\n",
    "        arr1.sort(key=mycmp)\n",
    "\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        indexi = 0\n",
    "        for i in range(len(arr2)):\n",
    "            for j in range(indexi, len(arr1)):\n",
    "                if arr1[j] == arr2[i]:\n",
    "                    tmp = arr1[j]\n",
    "                    arr1[j] = arr1[indexi]\n",
    "                    arr1[indexi] = tmp\n",
    "                    indexi += 1\n",
    "\n",
    "        for j in range(indexi, len(arr1)):\n",
    "            for i in range(indexi, len(arr1) - (j - indexi) - 1):\n",
    "                if arr1[i] > arr1[i + 1]:\n",
    "                    tmp = arr1[i]\n",
    "                    arr1[i] = arr1[i + 1]\n",
    "                    arr1[i + 1] = tmp\n",
    "        return arr1\n",
    "        \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
